/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        654.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/14 20:38
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
//
//二叉树的根是数组 nums 中的最大元素。
//左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
//右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
//返回有给定数组 nums 构建的 最大二叉树 。
#include "../header.h"

class Solution {
public:
    TreeNode *constructMaximumBinaryTree(vector<int> &nums) {
        return build(nums, 0, nums.size() - 1);
    }

private:
    TreeNode *build(vector<int> &nums, int lo, int hi) {
        if (lo > hi)
            return nullptr;
        int max = nums[lo];
        int index = lo;
        for (int i = lo + 1; i <= hi; ++i) {
            if (nums[i] > max) {
                max = nums[i];
                index = i;
            }
        }

        TreeNode *root = new TreeNode(max);
        root->left = build(nums, lo, index - 1);
        root->right = build(nums, index + 1, hi);
        return root;
    }
};
